// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package modload

import (
	"cmd/go/internal/mvs"
	"context"
	"reflect"
	"sort"

	"golang.org/x/mod/module"
	"golang.org/x/mod/semver"
)

// editRequirements返回rs的编辑版本，例如：
// 
// 1。选择mustSelect中的每个模块版本。
// 
// 2。tryUpgrade中的每个模块版本在不违反（1）的情况下尽可能升级到指定的
// 版本。
// 
// 3。rs.rootModules（或rs.graph，如果rs未运行）
// 中的每个模块版本仅从其原始版本降级到满足（1）所需的程度，或仅升级到满足（1）和
// （2）所需的程度。
// 
// 4。在rs的
// 依赖关系图、
// mustSelect中版本的组合依赖关系图或
// tryUpgrade中每个单独模块版本的依赖关系中，没有任何模块升级超过其路径的最大版本。
// 
// 通常情况下，mustSelect中的模块版本是由于模块或模块内的
// 包将显式命令行参数与“go 
// get”匹配，tryUpgrade中的版本是可传递的依赖项，
// 要么通过“go get-u”进行升级，要么添加以满足某些
// 否则缺少包导入。
func editRequirements(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) {
	limiter, err := limiterForEdit(ctx, rs, tryUpgrade, mustSelect)
	if err != nil {
		return rs, false, err
	}

	var conflicts []Conflict
	for _, m := range mustSelect {
		conflict, err := limiter.Select(m)
		if err != nil {
			return rs, false, err
		}
		if conflict.Path != "" {
			conflicts = append(conflicts, Conflict{
				Source: m,
				Dep:    conflict,
				Constraint: module.Version{
					Path:    conflict.Path,
					Version: limiter.max[conflict.Path],
				},
			})
		}
	}
	if len(conflicts) > 0 {
		return rs, false, &ConstraintError{Conflicts: conflicts}
	}

	mods, changed, err := selectPotentiallyImportedModules(ctx, limiter, rs, tryUpgrade)
	if err != nil {
		return rs, false, err
	}

	var roots []module.Version
	if rs.pruning == unpruned {
		// 在没有图修剪的模块中，提供由主模块导入的包的模块可以是显式根，也可以是隐式传递的
		// 依赖项。我们将mustSelect中的模块提升为明确的
		// 要求。
		var rootPaths []string
		for _, m := range mustSelect {
			if m.Version != "none" && !MainModules.Contains(m.Path) {
				rootPaths = append(rootPaths, m.Path)
			}
		}
		if !changed && len(rootPaths) == 0 {
			// 构建列表没有更改，我们没有新的根添加。
			// 我们不需要重新计算模块的最小根。
			return rs, false, nil
		}

		for _, m := range mods {
			if v, ok := rs.rootSelected(m.Path); ok && (v == m.Version || rs.direct[m.Path]) {
				// m.Path以前是根目录，其版本没有改变，或者
				// 我们认为它提供了一个由包
				// 或主模块中的测试直接导入的包。现在我们假设它仍然是
				// 相关的，足以保持根。如果我们真的在主模块中加载了所有的
				// 包和测试（我们在这里没有这样做），
				// 我们可以在那时修改显式根。
				rootPaths = append(rootPaths, m.Path)
			}
		}

		roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: mods})
		if err != nil {
			return nil, false, err
		}
	} else {
		// 在具有修剪图的模块中，主模块导入的每个提供包
		// 的模块必须保留为根。
		roots = mods
		if !changed {
			// 因为我们刚才计算的根是不变的，所以整个图必须与之前相同。保存原始rs，因为我们有
			// 可能已经加载了它的需求图。
			return rs, false, nil
		}
	}

	// 甚至不在构建列表中的模块必然无法提供任何导入的包。仅将
	// 仍在生成列表中的直接模块标记为直接。
	// 
	// TODO（bcmills）：将直接映射保持为
	// 但允许它引用不再在构建列表中的模块，这更有意义吗？
	// 这可能会使UpdateRoot变得复杂，但在其他方面可能会更干净。
	direct := make(map[string]bool, len(rs.direct))
	for _, m := range roots {
		if rs.direct[m.Path] {
			direct[m.Path] = true
		}
	}
	return newRequirements(rs.pruning, roots, direct), changed, nil
}

// limiterForEdit返回一个版本限制器，其最大版本设置为：
// mustSelect中每个模块路径的最大版本为此处列出的版本
// ，其他模块路径的最大版本为rs的依赖关系图中找到的路径的最大版本
// ，mustSelect中版本的组合依赖关系
// 图表，或tryUpgrade中每个单独
// 模块版本的依赖关系。
func limiterForEdit(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (*versionLimiter, error) {
	mg, err := rs.Graph(ctx)
	if err != nil {
		return nil, err
	}

	maxVersion := map[string]string{} // 模块路径→ 版本
	restrictTo := func(m module.Version) {
		v, ok := maxVersion[m.Path]
		if !ok || cmpVersion(v, m.Version) > 0 {
			maxVersion[m.Path] = m.Version
		}
	}

	if rs.pruning == unpruned {
		// 开始。不支持图形修剪的mod文件并不表明哪个
		// 可传递依赖项实际上与主模块相关，因此我们
		// 必须假设任何可以提供任何包的模块——
		// 也就是说，任何选择的版本不是“无”的模块——都可能与
		// 相关。快走。mod file显式记录主模块导入的每个提供包
		for _, m := range mg.BuildList() {
			restrictTo(m)
		}
	} else {
		// 的模块。
		// 
		// 如果我们需要降级在
		// tryUpgrade中找到的现有根或新根，我们不想让降级意外地将主模块导入的模块升级为任意版本。
		// 然而，我们并不特别关心对模块
		// 的任意升级，这些模块（最多）只提供通过测试
		// 主模块之外的依赖项导入的包。
		for _, m := range rs.rootModules {
			restrictTo(module.Version{
				Path:    m.Path,
				Version: mg.Selected(m.Path),
			})
		}
	}

	if err := raiseLimitsForUpgrades(ctx, maxVersion, rs.pruning, tryUpgrade, mustSelect); err != nil {
		return nil, err
	}

	// mustSelect中的版本会覆盖我们天真地选择的任何模块-
	// 我们将根据需要降级其他模块，以满足它们的要求。
	for _, m := range mustSelect {
		restrictTo(m)
	}

	return newVersionLimiter(rs.pruning, maxVersion), nil
}

// raiseLimitsForUpgrades将maxVersions中的模块版本增加到
// /版本，以允许tryUpgrade中的每个模块
// （单独或任意组合）以及mustSelect中的所有模块同时添加为根。
// 
// maxVersion中不存在的版本是不受限制的，并且假设
// 它们不会被提升到根需求（因此，如果主模块支持图形修剪，则不会贡献
// 它们自己的依赖项）。
// 
// 如果为了选择
// 附带降级的一部分提供了上限。
// mustSelect中的版本而需要降级，这些限制为模块升级为
func raiseLimitsForUpgrades(ctx context.Context, maxVersion map[string]string, pruning modPruning, tryUpgrade []module.Version, mustSelect []module.Version) error {
	// allow将m.Path的限制至少提高到m.Version。
	// 如果m.路径已经不受限制，那么它仍然不受限制。
	allow := func(m module.Version) {
		v, ok := maxVersion[m.Path]
		if !ok {
			return // m.路径不受限制。
		}
		if cmpVersion(v, m.Version) < 0 {
			maxVersion[m.Path] = m.Version
		}
	}

	var (
		unprunedUpgrades []module.Version
		isPrunedRootPath map[string]bool
	)
	if pruning == unpruned {
		unprunedUpgrades = tryUpgrade
	} else {
		isPrunedRootPath = make(map[string]bool, len(maxVersion))
		for p := range maxVersion {
			isPrunedRootPath[p] = true
		}
		for _, m := range tryUpgrade {
			isPrunedRootPath[m.Path] = true
		}
		for _, m := range mustSelect {
			isPrunedRootPath[m.Path] = true
		}

		allowedRoot := map[module.Version]bool{}

		var allowRoot func(m module.Version) error
		allowRoot = func(m module.Version) error {
			if allowedRoot[m] {
				return nil
			}
			allowedRoot[m] = true

			if MainModules.Contains(m.Path) {
				// 主要模块版本已经被认为比任何
				// 可能的m都高，因此m不能被选为根，扫描其依赖项也没有意义。
				return nil
			}

			allow(m)

			summary, err := goModSummary(m)
			if err != nil {
				return err
			}
			if summary.pruning == unpruned {
				// 为了提高效率，我们将把所有未运行的升级加载为一个大的
				// 图，而不是单独加载每个升级的（可能重叠的）子图。
				unprunedUpgrades = append(unprunedUpgrades, m)
				return nil
			}
			for _, r := range summary.require {
				if isPrunedRootPath[r.Path] {
					// r可能因升级或降级而成为根目录，在这种情况下，其依赖项将不会被删除。
					// 我们需要允许这些依赖项也升级。
					if err := allowRoot(r); err != nil {
						return err
					}
				} else {
					// r不会成为根，所以它的依赖关系无关紧要。
					// 只允许r本身。
					allow(r)
				}
			}
			return nil
		}

		for _, m := range tryUpgrade {
			allowRoot(m)
		}
	}

	if len(unprunedUpgrades) > 0 {
		// 计算所有未运行升级的最大版本。
		// 由于这些模块未运行，我们最终将扫描它们的所有
		// 可传递依赖项，无论最终选择哪个版本，
		// 由于我们有一个大的依赖关系图要扫描，我们可能会得到
		// 不重新访问
		// 多个升级中的常见版本的依赖关系会带来很大的好处。
		upgradeGraph, err := readModGraph(ctx, unpruned, unprunedUpgrades)
		if err != nil {
			// 计算从tryUpgrade中的模块路径到
			// 错误的需求路径，以及从rs.rootModules到
			// tryUpgrade模块路径的需求路径（如果有）。返回a*mvs。BuildListError显示
			// 路径的串联（中间有一个升级）。
			return err
		}

		for _, r := range upgradeGraph.BuildList() {
			// 升级到m将升级到r，调用方要求我们
			// 尝试升级到m，所以升级到r是可以的。
			allow(r)
		}
	}

	// 明确允许mustSelect隐含的任何（传递性）升级。
	nextRoots := append([]module.Version(nil), mustSelect...)
	for nextRoots != nil {
		module.Sort(nextRoots)
		rs := newRequirements(pruning, nextRoots, nil)
		nextRoots = nil

		rs, mustGraph, err := expandGraph(ctx, rs)
		if err != nil {
			return err
		}

		for _, r := range mustGraph.BuildList() {
			// mustSelect中的某些模块需要r，因此我们必须至少允许
			// r.Version（除非它与mustSelect中的另一个条目冲突，在
			// 这种情况下，我们将以任何方式出错）。
			allow(r)

			if isPrunedRootPath[r.Path] {
				if v, ok := rs.rootSelected(r.Path); ok && r.Version == v {
					// r已经是根目录，所以它的需求已经包含在构建列表中。
					continue
				}

				// mustSelect中的依赖项可能会升级（或降级）现有的
				// 根目录以匹配r，该根目录将保留为根目录。然而，由于r不是rs的根，因此它的依赖项已从这个构建
				// 列表中删除。我们需要明确地将其添加回去，这样我们就可以允许任何
				// r将引入的过渡升级。
				if nextRoots == nil {
					nextRoots = rs.rootModules // 已封顶
				}
				nextRoots = append(nextRoots, r)
			}
		}
	}

	return nil
}

// 选择潜在导入的模块增加了
// rs中可能提供主模块导入的包（直接或间接）的每个模块，以及tryUpgrade中的每个模块，朝向
// rs或tryUpgrade中看到的最高版本，但不超过限制器强制
// 的最大值。
// 
// 它返回限制器选择的模块版本列表，按
// 路径排序，并带有一个布尔值，指示该列表是否与从rs读取的模块列表不同。
func selectPotentiallyImportedModules(ctx context.Context, limiter *versionLimiter, rs *Requirements, tryUpgrade []module.Version) (mods []module.Version, changed bool, err error) {
	for _, m := range tryUpgrade {
		if err := limiter.UpgradeToward(ctx, m); err != nil {
			return nil, false, err
		}
	}

	var initial []module.Version
	if rs.pruning == unpruned {
		mg, err := rs.Graph(ctx)
		if err != nil {
			return nil, false, err
		}
		initial = mg.BuildList()[MainModules.Len():]
	} else {
		initial = rs.rootModules
	}
	for _, m := range initial {
		if err := limiter.UpgradeToward(ctx, m); err != nil {
			return nil, false, err
		}
	}

	mods = make([]module.Version, 0, len(limiter.selected))
	for path, v := range limiter.selected {
		if v != "none" && !MainModules.Contains(path) {
			mods = append(mods, module.Version{Path: path, Version: v})
		}
	}

	// 我们已经为每个模块确定了可接受的版本，但那些
	// 版本之间不一定一致：一个升级或
	// 降级的模块可能需要更高（但仍然允许）版本的
	// 另一个。较低版本可能需要与
	// /实际无关的额外依赖项，因此我们需要计算实际选择的版本。
	mg, err := readModGraph(ctx, rs.pruning, mods)
	if err != nil {
		return nil, false, err
	}
	mods = make([]module.Version, 0, len(limiter.selected))
	for path, _ := range limiter.selected {
		if !MainModules.Contains(path) {
			if v := mg.Selected(path); v != "none" {
				mods = append(mods, module.Version{Path: path, Version: v})
			}
		}
	}
	module.Sort(mods)

	changed = !reflect.DeepEqual(mods, initial)

	return mods, changed, err
}

// 版本限制程序跟踪每个模块可能选择的版本
// 受可传递依赖项的最大版本限制。
type versionLimiter struct {
	// 剪枝是加载传递给
	// Select和UPGRADETOR的模块依赖项的剪枝。
	pruning modPruning

	// max将每个模块路径映射到可为该路径选择的最大版本。
	// 
	// 没有条目的路径是不受限制的，我们假设它们不会被提升为根依赖项（因此，如果
	// 主模块支持图形修剪，则不会贡献依赖项）。
	max map[string]string

	// 选中的将每个模块路径映射到该路径的一个版本（如果已知），其
	// 可传递依赖项不违反任何max版本。对于给定的
	// 的版本都是最高的。
	// 模块路径，在任何UpgradeToward调用过程中，保持
	// 
	// 如果在为
	// 调用UpgradeToward时发现更高的可接受版本，则不会更新所选版本。
	// 忽略这些版本会使两个模块的降级计算结果与每个模块的单独降级计算结果接近。（一个模块影响另一个模块的唯一方式是一个模块的最终降级版本明确要求另一个模块的更高版本。）
	// 
	// 每个模块的版本“none”始终不违反任何max 
	// 版本，因此版本“none”处的路径被省略。
	selected map[string]string

	// dqReason记录每个遇到的版本是否以及为什么是
	// 。
	dqReason map[module.Version]dqState

	// 需要将每个尚未取消资格的模块版本映射到直接需要它的版本
	// 上。如果该版本被取消资格，
	// 取消资格将被传播到列表中的所有版本。
	requiring map[module.Version][]module.Version
}

// dqState表示模块版本是否以及为什么会被
// 以符合其要求的方式使用。
// 
// 零dqState表示未知模块版本为
// 不合格，原因可能是该版本正常，也可能是我们目前正在遍历
// 一个包含它的循环。
type dqState struct {
	err      error          // 如果非零，则不合格，因为无法读取模块的要求
	conflict module.Version // 不合格，因为模块（传递）需要dep，超过其路径的最大版本限制
}

func (dq dqState) isDisqualified() bool {
	return dq != dqState{}
}

// newVersionLimiter返回一个版本限制程序，该程序限制在max中显示为键的模块路径
// 。
// 
// max将每个模块路径映射到其最大版本；地图中不存在
// 的路径不受限制。限制器假定不受限制的路径
// 不会升级为根依赖项。
// 
// 如果模块图修剪生效，那么如果传递给
// UpgradeToward或Select的模块支持修剪，则在扫描需求时跳过其不受限制的依赖项。
func newVersionLimiter(pruning modPruning, max map[string]string) *versionLimiter {
	selected := make(map[string]string)
	for _, m := range MainModules.Versions() {
		selected[m.Path] = m.Version
	}
	return &versionLimiter{
		pruning:   pruning,
		max:       max,
		selected:  selected,
		dqReason:  map[module.Version]dqState{},
		requiring: map[module.Version][]module.Version{},
	}
}

// 升级尝试将所选m.Path版本升级到尽可能接近
// 的m.version，而不违反l的最大版本限制。
// 
// 如果模块图修剪生效，且m本身支持修剪，则不会遵循
// m的非限制依赖项的依赖项。
func (l *versionLimiter) UpgradeToward(ctx context.Context, m module.Version) error {
	selected, ok := l.selected[m.Path]
	if ok {
		if cmpVersion(selected, m.Version) >= 0 {
			// 所选版本已至少为m，因此无需升级。
			return nil
		}
	} else {
		selected = "none"
	}

	if l.check(m, l.pruning).isDisqualified() {
		candidates, err := versions(ctx, m.Path, CheckAllowed)
		if err != nil {
			// 这很可能是到达存储库的暂时性错误，而不是检索到的版本的永久性错误。
			// 
			// TODO（golang.org/issue/31730，golang.org/issue/30134）：
			// 根据实际错误解码该做什么。
			return err
		}

		// 跳转到<m.Version的候选。
		i := sort.Search(len(candidates), func(i int) bool {
			return semver.Compare(candidates[i], m.Version) >= 0
		})
		candidates = candidates[:i]

		for l.check(m, l.pruning).isDisqualified() {
			n := len(candidates)
			if n == 0 || cmpVersion(selected, candidates[n-1]) >= 0 {
				// 我们在已经选择的版本之上找不到合适的候选版本。
				// 保留该版本不修改。
				return nil
			}
			m.Version, candidates = candidates[n-1], candidates[:n-1]
		}
	}

	l.selected[m.Path] = m.Version
	return nil
}

// Select尝试将所选的m.Path版本设置为m.version。
func (l *versionLimiter) Select(m module.Version) (conflict module.Version, err error) {
	dq := l.check(m, l.pruning)
	if !dq.isDisqualified() {
		l.selected[m.Path] = m.Version
	}
	return dq.conflict, dq.err
}

// 检查确定m（或其可传递依赖项）是否会违反l的
// 如果添加到模块需求图中，最大版本限制。
// 
// 如果剪枝生效，并且m本身支持图形剪枝，则不会遵循m的非限制依赖的依赖关系
// 。如果到目前为止，主模块的图剪枝
// 不变量仍然有效，那么这些
// 模块中的包最多只能通过从外部模块加载的依赖项测试导入。尽管我们希望尽可能保持
// “全部测试”的可复制性，但我们不希望保留测试
// 相关性，这些相关性充其量只是略微相关。
func (l *versionLimiter) check(m module.Version, pruning modPruning) dqState {
	if m.Version == "none" || m == MainModules.mustGetSingleMainModule() {
		// 版本“无”没有要求，目标的依赖关系是
		// 重复的。
		return dqState{}
	}

	if dq, seen := l.dqReason[m]; seen {
		return dq
	}
	l.dqReason[m] = dqState{}

	if max, ok := l.max[m.Path]; ok && cmpVersion(m.Version, max) > 0 {
		return l.disqualify(m, dqState{conflict: m})
	}

	summary, err := goModSummary(m)
	if err != nil {
		// 如果我们不能加载需求，我们就不能加载go。mod文件。
		// 出现这种情况的原因有很多，但这通常意味着较旧版本的模块缺少或无效的
		// go。mod文件。举个例子，如果举个例子。com/mod发布了v2。0.0之前
		// 迁移到模块（v2.0.0+不兼容），然后添加有效的go。mod 
		// 在v2中。0.1，从v2降级。0.1将导致此错误。
		// 
		// TODO（golang.org/issue/31730，golang.org/issue/30134）：如果错误
		// 是暂时的（我们无法下载go.mod），请从
		// 降级返回错误。目前，我们无法判断这是什么样的错误。
		return l.disqualify(m, dqState{err: err})
	}

	if summary.pruning == unpruned {
		pruning = unpruned
	}
	for _, r := range summary.require {
		if pruning == pruned {
			if _, restricted := l.max[r.Path]; !restricted {
				// r.路径是不受限制的，所以我们不关心选择哪个版本。我们假设r.Path不会成为根依赖项，因此
				// 因为m支持修剪，所以不会遵循r的依赖项。
				continue
			}
		}

		if dq := l.check(r, pruning); dq.isDisqualified() {
			return l.disqualify(m, dq)
		}

		// r及其依赖项（可能暂时）正常。
		// 
		// 然而，如果需求图中有循环，我们可能只检查了部分需求图，而r（以及m）可能会被我们尚未访问的路径取消资格。记住这条边
		// 这样，如果出现这种情况，我们可以取消m及其依赖项的资格。
		l.requiring[r] = append(l.requiring[r], m)
	}

	return dqState{}
}

// 取消m（或其传递依赖项之一）
// 违反l的最大版本限制的记录。
func (l *versionLimiter) disqualify(m module.Version, dq dqState) dqState {
	if dq := l.dqReason[m]; dq.isDisqualified() {
		return dq
	}
	l.dqReason[m] = dq

	for _, p := range l.requiring[m] {
		l.disqualify(p, dqState{conflict: m})
	}
	// 现在我们已经取消了依赖于m的模块的资格，我们可以忘记关于它们的
	// 了，我们不需要再次取消它们的资格。
	delete(l.requiring, m)
	return dq
}
